package l.l.w.leetcode._0124BinaryTreeMaximumPathSum;

/**
 * Created by llw on 2018/5/15/0015.
 */
public class _0124BinaryTreeMaximumPathSum {

    public int maxPathSum(TreeNode root) {
        if(root == null) return 0;
        int[] record = new int[1];
        return postOrder(root, record);
    }
    private int postOrder(TreeNode root, int[] record){
//        if(root == null){
//            record[0] = 0;
//            return 0;
//        }
        int lMax, maxFromLeft, rMax, maxFromRight;
        if(root.left == null){
            lMax = root.val;
            maxFromLeft = 0;
        }else{
            lMax = postOrder(root.left, record);
            maxFromLeft = record[0];
        }
        if(root.right == null){
            rMax = root.val;
            maxFromRight = 0;
        }else{
            rMax = postOrder(root.right, record);
            maxFromRight = record[0];
        }
        record[0] = Math.max(Math.max(maxFromLeft,maxFromRight) + root.val,root.val);
        int cur = Math.max(maxFromLeft + maxFromRight + root.val,record[0]);
        return Math.max(Math.max(lMax,rMax),cur);
    }

    public static void main(String[] args) {
//        TreeNode root = new TreeNode(-10);
//        TreeNode left = new TreeNode(9);
//        TreeNode right = new TreeNode(20);
//        root.left = left;
//        root.right = right;
//        TreeNode left1 = new TreeNode(15);
//        TreeNode right1 = new TreeNode(7);
//        right.left = left1;
//        right.right = right1;

        TreeNode root = new TreeNode(9);
        TreeNode left = new TreeNode(6);
        TreeNode right = new TreeNode(-3);
        root.left = left;
        root.right = right;
        TreeNode left1 = new TreeNode(-6);
        TreeNode right1 = new TreeNode(2);
        right.left = left1;
        right.right = right1;


        TreeNode left2 = new TreeNode(2);
        right1.left = left2;

        TreeNode left3 = new TreeNode(-6);
        TreeNode right3 = new TreeNode(-6);
        left2.left = left3;
        left2.right = right3;

        TreeNode left4 = new TreeNode(-6);
        left3.left = left4;
        int result = new _0124BinaryTreeMaximumPathSum().maxPathSum(root);
        System.out.println(result);

    }
}
class TreeNode {
     int val;
     TreeNode left;
     TreeNode right;
     TreeNode(int x) { val = x; }
 }
